public class Solution6 {
    //零钱兑换Ⅱ
    public static int change(int amount, int[] coins) {
            int n = coins.length;

            // int[][] dp = new int[n+1][amount+1];
            //  for (int i = 0; i < n+1; i++) {
            //     dp[i][0] = 1;
            //  }
            // for (int i = 1; i < n+1; i++) {
            //     for (int j = 1; j < amount+1; j++) {
            //             dp[i][j] += dp[i-1][j];

            //         if (j >= coins[i-1]) {
            //             dp[i][j] += dp[i][j-coins[i-1]];
            //         }
            //     }
            // }

            //优化版本，滚动数组
            int[] dp = new int[amount+1];
            dp[0] = 1;
            for (int i : coins) {
                for (int j = i; j < amount+1; j++) {

                    dp[j] += dp[j-i];

                }
            }
            return dp[amount];
        }

    public static void main(String[] args) {
        int amount = 5;
        int[] coins = {1,2,5};
        int ret  = change(amount,coins);
        System.out.println(ret);
    }
}
